package com.leetcode.matrix;

import java.util.LinkedList;

public class LargestRectangleArea {
    public static void main(String[] args) {

    }

    public int largestRectangleArea(int[] heights) {
        LinkedList<Integer> stack = new LinkedList<>();
        int len = heights.length;
        int[] newHeights = new int[len + 2];
        newHeights[0] = 0;
        newHeights[len + 1] = 0;
        for (int i = 0; i < len; i++) {
            newHeights[i+1] = heights[i];
        }
        int res = 0;
        for (int i = 0; i < newHeights.length; i++) {
            while(!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]) {
                int cur = stack.pop();
                int curHeight = newHeights[cur];
                int leftIndex = stack.peek();
                int rightIndex = i;
                int curWidth = rightIndex - leftIndex - 1;
                res = Math.max(res, curWidth * curHeight);
            }
            stack.push(i);
        }
        return res;
    }
}
